A public key cryptography technique ensures secure communication without sharing a key in advance. This technique has a problem of increasing size of the cryptosystem. Under the circumstance, a proposed method employs an algebraic torus so as to compress the size of the cryptosystem in the public key cryptography. Representation of elements of the algebraic torus includes trace representation, projective representation, and extension field representation. The trace representation is known to use an exponentiation algorithm, but multiplication is assumed not to be available. Therefore, the public key cryptography with algebraic torus has employed the trace representation for input and output in respective steps of key generation, encryption, and decryption. The public key cryptography has employed the projective representation or the extension field representation for computation. In view of this, there is a need for a conversion (representation conversion) between the respective representations before and after the computation.
However, such a conventional technique increases in calculation amount in the representation conversion depending on a combination of representations before and after the conversion. This may considerably increase the amount of calculation including representation conversion and computation.